/********************************************************************************************
 Author       : LIN
 Email        : l2441473911@163.com
 LastModified : 2020-12-24 13:40
 FileName     : priority-queue.c
 Description  : min-heap implementation of a priority queue, elements are universal pointers, 
                each is assumed to point to the start of the address of an integer in memory.
				Comparasions are made by comparing the integer each element points. This
				implementation make use of a sentinel element in the front (index 0) of the 
				heap array whose corresponding data is assumed to be smaller than that of any 
				other elements (INT_MIN). Thus the real heap structure start at index 1.
*******************************************************************************************/
#include "./priority-queue.h"

Heap *BuildHeap(HeapElement *source_array, int size, int heap_capacity){
	int i, j, smallerChild;
	HeapElement *heapArray, sentinel, data;

	Heap *newHeap = (Heap *)malloc(sizeof(Heap));
	heapArray = (HeapElement *)malloc(sizeof(HeapElement) * (1 + heap_capacity));

	// set sentinel
	sentinel = (int *)malloc(sizeof(int));
	DerefAsInt(sentinel) = INT_MIN;
	heapArray[0] = sentinel;

	newHeap->heap_size = 0;
	newHeap->heap_capacity = heap_capacity;
	newHeap->heap_array = heapArray;

	if(source_array != NULL && size > 0){
		// copy over the source data
		newHeap->heap_size = size;
		for(i = 0; i < size; i++){
			heapArray[i + 1] = source_array[i];
		}


		// percolate down from the last parent
		for(i = size / 2; i > 0; i--){
			data = heapArray[i];
			for(j = i; j * 2 <= size ;j = smallerChild){
				smallerChild = 2 * j;
				if(smallerChild < size && DerefAsInt(heapArray[smallerChild + 1]) < DerefAsInt(heapArray[smallerChild]))
					smallerChild++;

				if(DerefAsInt(heapArray[smallerChild]) < DerefAsInt(data))
					heapArray[j] = heapArray[smallerChild];
				else break;
			}
			heapArray[j] = data;

		}
	}
	
	return newHeap;
}

int HeapInsert(Heap *h, HeapElement e){
	if(h == NULL || h->heap_size >= h->heap_capacity) return 0;

	int i, eData = DerefAsInt(e);

	h->heap_array[++(h->heap_size)] = e;

	// percolate up
	for(i = h->heap_size; eData < DerefAsInt(h->heap_array[i/2]); i/=2)
		h->heap_array[i] = h->heap_array[i/2];
	h->heap_array[i] = e;

	return 1;
}

HeapElement HeapPopMin(Heap *h){
	if(h == NULL) return HEAP_ELEMENTTYPE_ERROR_VAL;
	
	int i, smallerChild;

	HeapElement extracted_min = h->heap_array[1], data;
	
	h->heap_array[1] = h->heap_array[h->heap_size];
	h->heap_size--;

	data = h->heap_array[1];
	for(i = 1; i * 2 <= h->heap_size; i = smallerChild){
		smallerChild = i * 2;
		if(smallerChild < h->heap_size && DerefAsInt(h->heap_array[smallerChild + 1]) < DerefAsInt(h->heap_array[smallerChild]))
			smallerChild++;

		if(DerefAsInt(h->heap_array[smallerChild]) < DerefAsInt(data))
			h->heap_array[i] = h->heap_array[smallerChild];
		else break;
	}
	h->heap_array[i] = data; 

	return extracted_min;
}


void DisposeHeap(Heap *h){
	if(h != NULL){
		// free sentinel
		free(h->heap_array[0]);

		free(h->heap_array);
		free(h);
	}
}
